from typing import List


from itertools import product
from typing import Dict, Tuple, Set
Island = Tuple[int, int]

class Solution(object):
    @staticmethod
    def make_group(line) -> List[Island]:
        res = []
        start = -1
        for i in range(len(line)):
            if start == -1 and line[i] == '1':
                start = i
            if start != -1 and line[i] == '0':
                res.append((start, i))
                start = -1
        if start != -1:
            res.append((start, len(line)))
        return res

    @staticmethod
    def dict_append(d: Dict[Island, List[Island]], k:Island, v:Island):
        if k in d:
            d[k].append(v)
        else:
            d[k] = [v]

    def is_link(self, island1: Island, island2: Island):
        s1, e1 = island1
        s2, e2 = island2
        return s1 < e2 and s2 < e1

    def merge_parents(self, pairs):
        islands: Set[int] = set([i1 for i1, i2 in pairs]).union(set([i2 for i1, i2 in pairs]))
        path = {}
        for i1, i2 in pairs:
            self.dict_append(path, i1, i2)
            self.dict_append(path, i2, i1)
        group_res = {island: -1 for island in islands}

        def _walk(start, number):
            res = [start]
            for n in path[start]:
                if group_res[n] == -1:
                    group_res[n] = number
                    res.extend(_walk(n, number))
            return res

        # walk
        all_groups = []
        for island in islands:
            if group_res[island] != -1:
                continue
            group_res[island] = len(all_groups)
            all_groups.append(_walk(island, len(all_groups)))
        return all_groups


    def numIslands(self, grid: List[List[str]], i=0, parents: List[List[Island]]=None, res=0) -> int:
        # print(parents, res)
        if parents is None:
            parents = []
        if i == len(grid):  # Final
            return res + len(parents)
        islands = self.make_group(grid[i])

        # 展开父岛，以避免双重循环
        parents_flatten = []
        parents_ids = []
        for j, group in enumerate(parents):
            parents_flatten.extend(group)
            parents_ids.extend([j] * len(group))

        # 父岛与当前岛之间的相连关系
        p2n = {}
        for i1, i2 in product(islands, parents_flatten):
            if self.is_link(i1, i2):
                self.dict_append(p2n, i2, i1)

        # 更新res，即增加父岛中无后继的数量
        for group in parents:
            if all([p_island not in p2n for p_island in group]):
                res += 1

        # 当前岛对应的父岛索引
        ns: Dict[Island, int] = {island: -1 for island in islands}
        # 合并的索引
        merged: Set[(int, int)] = set()
        for j, p in zip(parents_ids, parents_flatten):
            if p not in p2n:
                continue
            for now_island in p2n[p]:
                if ns[now_island] != -1 and ns[now_island] != j:
                    merged.add((ns[now_island], j))
                ns[now_island] = j

        # 按照父岛的关系，合并当前岛的类别
        parent_merged = self.merge_parents(merged)
        for g in parent_merged:
            for k, v in ns.items():
                if v in g[1:]:
                    ns[k] = g[0]

        # 当前岛的现况合并
        ng = []
        for v in set(ns.values()):
            if v != -1:
                ng.append([k for k, nv in ns.items() if nv == v])
            else:
                ng.extend([[k] for k, nv in ns.items() if nv == v])
        # print('ng', ng)

        return self.numIslands(grid, i+1, ng, res)

if __name__ == '__main__':
    s = Solution()
    # print(s.is_link((0, 2), (2, 3)))

    grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["1","1","0","0","0"],
        ["0","0","0","0","0"]
    ]
    print(s.numIslands(grid))
    grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
    ]
    print(s.numIslands(grid))
    grid = [
        ["1","0","1","1","0","0","1","0","1","1","1","1","0","1","0","1","1","1","1","0"],
        ["0","1","0","0","1","0","1","0","1","1","1","1","1","1","0","1","1","0","1","1"],
        ["1","0","0","1","0","1","0","1","0","1","1","0","1","1","1","0","0","1","1","0"],
        ["0","1","1","0","0","1","1","0","1","1","1","1","0","0","1","0","0","0","1","1"],
        ["1","1","0","1","0","0","1","0","0","0","1","0","1","0","1","1","1","0","1","1"],
        ["0","0","0","0","1","0","1","1","0","0","1","0","0","1","0","1","1","1","1","0"],
        ["1","0","1","1","1","1","0","1","1","0","1","1","0","1","1","1","0","0","1","0"],
        ["0","1","1","0","0","0","1","0","0","1","0","1","1","1","0","0","1","1","0","1"],
        ["0","0","0","0","1","1","0","1","0","0","1","1","0","1","0","0","1","0","1","0"],
        ["0","0","1","1","1","0","1","0","1","0","1","1","1","0","1","1","1","1","1","0"],
        ["1","0","1","0","1","1","1","0","1","1","1","0","1","0","1","0","1","0","1","1"],
        ["0","0","1","1","1","1","0","1","1","1","0","1","0","0","0","1","1","1","0","1"],
        ["1","1","1","0","0","0","0","0","1","1","0","1","1","1","0","1","1","1","1","0"],
        ["0","0","1","1","1","0","0","1","0","0","1","1","1","1","1","1","0","1","1","0"],
        ["0","0","0","1","1","0","0","0","0","1","1","0","1","0","0","1","1","1","1","1"],
        ["0","1","1","1","0","1","0","0","1","1","1","1","1","0","1","1","1","0","0","1"],
        ["0","0","0","0","1","1","1","1","0","0","0","0","1","0","0","0","0","1","1","0"],
        ["1","1","1","1","1","1","1","1","1","1","0","1","1","0","1","1","1","1","1","1"],
        ["0","1","0","0","1","0","0","1","1","1","1","1","1","0","1","0","1","1","1","1"],
        ["0","0","1","1","1","1","1","0","0","0","1","1","1","1","1","1","0","1","1","0"]
    ]
    print(s.numIslands(grid))

    # s.merge_parents(((2,3), (3, 4), (5,6)))
